﻿#define _CRT_SECURE_NO_WARNINGS 1
//集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
//
//给定一个数组 nums 代表了集合 S 发生错误后的结果。
//
//请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
//
//
//
//示例 1：
//
//输入：nums = [1, 2, 2, 4]
//输出：[2, 3]
//示例 2：
//
//输入：nums = [1, 1]
//输出：[1, 2]
//
//来源：力扣（LeetCode）
//链接：https ://leetcode-cn.com/problems/set-mismatch
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
//法一
//将数组排序之后，比较每对相邻的元素，即可找到错误的集合。
//
//寻找重复的数字较为简单，如果相邻的两个元素相等，则该元素为重复的数字。
//
//寻找丢失的数字相对复杂，可能有以下两种情况：
//
//如果丢失的数字大于 1 且小于 n，则一定存在相邻的两个元素的差等于 2，这两个元素之间的值即为丢失的数字；
//
//如果丢失的数字是 1 或 n，则需要另外判断。
//
//为了寻找丢失的数字，需要在遍历已排序数组的同时记录上一个元素，然后计算当前元素与上一个元素的差。考虑到丢失的数字可能是 1，
// 因此需要将上一个元素初始化为 0。
//
//当丢失的数字小于 nn 时，通过计算当前元素与上一个元素的差，即可得到丢失的数字；
//
//如果 \textit{ nums }[n - 1] \ne nnums[n−1]
//
//​
//= n，则丢失的数字是 nn。
//int cmp(int* a, int* b) {
//    return *a - *b;
//}
//
//int* findErrorNums(int* nums, int numsSize, int* returnSize) {
//    int* ret = malloc(sizeof(int) * 2);
//    *returnSize = 2;
//    qsort(nums, numsSize, sizeof(int), cmp);
//    int lastone = 0;
//    for (int i = 0; i < numsSize; i++) {
//        int cur = nums[i];
//        if (cur == lastone) {
//            ret[0] = lastone;
//        }
//        else if (cur - lastone > 1) {
//            ret[1] = lastone + 1;
//        }
//        lastone = cur;
//    }
//    if (nums[numsSize - 1] != numsSize)
//        ret[1] = numsSize;
//    return ret;
//}

//法二
//方法二：哈希表
//重复的数字在数组中出现 22 次，丢失的数字在数组中出现 00 次，其余的每个数字在数组中出现 11 次。
//因此可以使用哈希表记录每个元素在数组中出现的次数，然后遍历从 11 到 nn 的每个数字，分别找到出现 22 次和出现 00 次的数字，
//即为重复的数字和丢失的数字。

//int* findErrorNums(int* nums, int numsSize, int* returnSize)
//{
//    *returnSize = 2;
//    int* ret = (int*)calloc(*returnSize, sizeof(int));
//    int* arr = (int*)calloc(numsSize + 1, sizeof(int));
//    int old_sum = 0, cur_sum = 0, i = 0;
//    for (i = 0; i < numsSize; i++)
//    {
//        if (arr[nums[i]] == 1)
//        {
//            ret[0] = nums[i];
//        }
//        arr[nums[i]] = 1;
//        old_sum += i + 1;
//        cur_sum += nums[i];
//    }
//    ret[1] = old_sum - (cur_sum - ret[0]);
//    free(arr);
//    return ret;
//}

//描述
//小明同学最近开发了一个网站，在用户注册账户的时候，需要设置账户的密码，为了加强账户的安全性，小明对密码强度有一定要求：
//
//1. 密码只能由大写字母，小写字母，数字构成；
//
//2. 密码不能以数字开头；
//
//3. 密码中至少出现大写字母，小写字母和数字这三种字符类型中的两种；
//
//4. 密码长度至少为8
//
//现在小明受到了n个密码，他想请你写程序判断这些密码中哪些是合适的，哪些是不合法的。
//
//输入描述：
//输入一个数n，接下来有n(n≤100)行，每行一个字符串，表示一个密码，输入保证字符串中只出现大写字母，小写字母和数字，字符串长度不超过100。
//输出描述：
//输入n行，如果密码合法，输出YES，不合法输出NO
//示例1
//输入：
//1
//输出：
//YES
//#include<stdio.h>
//#include<string.h>
//int main()
//{
//    char arr[100];
//    int n, i, j, a = 0, b = 0, c = 0,flag=0;
//    scanf("%d", &n);
//    for (i = 0; i < n; i++)
//    {
//        scanf("%s", arr);
//        if (strlen(arr) < 8)
//        {
//            printf("NO\n");
//            continue;
//        }
//        if (isdigit(arr[0]) != 0)
//        {
//            printf("NO\n");
//            continue;
//        }
//        for (j = 0; j < strlen(arr); j++)
//        {
//            if (islower(arr[j]) != 0)
//            {
//                a++;
//            }
//            if (isupper(arr[j] != 0))
//            {
//                b++;
//            }
//            if (isdigit(arr[j]) != 0)
//            {
//                c++;
//            }
//            if (isdigit(arr[j]) + islower(arr[j]) + isupper(arr[j]) == 0)
//            {
//                flag = 1;
//                printf("NO\n");
//                break;
//          }
//        }
//        if (a == strlen(arr) || b == strlen(arr) || c == strlen(arr))
//        {
//            printf("NO\n");
//            continue;
//        }
//        if(flag==0)
//        printf("YES\n");
//        flag = 0;
//    }
//    return 0;
//}
//描述
//给定一个长度为 n 的非降序数组和一个非负数整数 k ，要求统计 k 在数组中出现的次数
//
//数据范围：0 \le n \le 1000, 0 \le k \le 1000≤n≤1000, 0≤k≤100，数组中每个元素的值满足 0 \le val \le 1000≤val≤100
//要求：空间复杂度 O(1)O(1)，时间复杂度 O(logn)O(logn)
//示例1
//输入：
//[1, 2, 3, 3, 3, 3, 4, 5], 3
//复制
//返回值：
//4
//方法：二分查找
//#include<stdio.h>
//int get_left_and_right(int* data, int datalen, int k, int flag)
//{
//    int left = 0, right = datalen - 1, mid;
//    while (left <= right)
//    {
//        mid = (left + right) / 2;
//        if (data[mid] > k)
//        {
//            right = mid - 1;
//        }
//        else if (data[mid] < k)
//        {
//            left = mid + 1;
//        }
//        else
//        {
//            if (flag == 0)
//            {
//                if (mid == left || data[mid - 1] != k)
//                    return mid;
//                else
//                    right = mid - 1;
//            }
//            else {
//                if (mid == right || data[mid + 1] != k)
//                    return mid;
//                else
//                    left = mid + 1;
//            }
//        }
//    }
//    return -1;
//}
//
//int GetNumberOfK(int* data, int dataLen, int k) {
//    if (dataLen == 0)return 0;
//    int left = get_left_and_right(data, dataLen, k, 0);
//    int right = get_left_and_right(data, dataLen, k, 1);
//    if (left == -1 && right == -1)
//        return 0;
//    return right - left + 1;
//}
//int main()
//{
//    int data[] = { 1,2,2,3,3,3,3,4 };
//    int count = GetNumberOfK(data, 8, 3);
//    printf("%d", count);
//    return 0;
//}
//整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。
//
//示例1 :
//
//输入：A = 29 （或者0b11101）, B = 15（或者0b01111）
//输出：2
//示例2 :
//
//输入：A = 1，B = 2
//输出：2
//
//其实就是多少位比特位不同
//#include<stdio.h>
//int convertInteger(int A, int B)
//{
//    int sum = A ^ B;
//    int count = 0, i;
//    for (i = 0; i < 32; i++)
//    {
//        if ((sum >> i) & 1 == 1)
//            count++;
//    }
//    return count++;
//}
//int main()
//{
//    int a, b;
//    scanf("%d%d", &a, &b);
//    int count = convertInteger(a, b);
//    printf("%d", count);
//    return 0;
//}
//给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。
//
//请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 - 1 。
//
//
//
//示例 1：
//
//输入：nums = [3, 6, 1, 0]
//输出：1
//解释：6 是最大的整数，对于数组中的其他整数，6 至少是数组中其他元素的两倍。6 的下标是 1 ，所以返回 1 。
//示例 2：
//
//输入：nums = [1, 2, 3, 4]
//输出： - 1
//解释：4 没有超过 3 的两倍大，所以返回 - 1 。
//示例 3：
//
//输入：nums = [1]
//输出：0
//解释：因为不存在其他数字，所以认为现有数字 1 至少是其他数字的两倍。

//int dominantIndex(int* nums, int numsSize)
//{
//    if (numsSize == 1)return 0;
//    int max, second, i, flag;
//    if (nums[0] > nums[1])
//    {
//        max = nums[0];
//        second = nums[1];
//        flag = 0;
//    }
//    else
//    {
//        max = nums[1];
//        second = nums[0];
//        flag = 1;
//    }
//    for (i = 2; i < numsSize; i++)
//    {
//        if (nums[i] > second && nums[i] < max)
//        {
//            second = nums[i];
//        }
//        else if (nums[i] > max)
//        {
//            second = max;
//            max = nums[i];
//            flag = i;
//        }
//    }
//    if (second * 2 <= max)
//        return flag;
//    else
//        return -1;
//}